// https://www.lintcode.com/problem/intersection/

public class Solution {
    /**
     * @param a: first sequence
     * @param b: second sequence
     * @return: return ans
     */
    public List<List<Integer>> Intersection(List<List<Integer>> a, List<List<Integer>> b) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        int prev_j = 0;
        for (int i = 0; i < a.size(); ++i) {
            List<Integer> _a = a.get(i);
            for (int j = prev_j; j < b.size(); ++j) {
                List<Integer> _b = b.get(j);
                if (_b.get(0) > _a.get(1)) {
                    break;
                }
                if (intersection(_a, _b)) {
                    List<Integer> r = new ArrayList<>();
                    r.add(i);
                    r.add(j);
                    ret.add(r);
                    prev_j = j;
                }
            }
        }
        return ret;
    }
    
    protected boolean intersection(List<Integer> a, List<Integer> b) {
        int v0_0 = a.get(0);
        int v0_1 = a.get(1);
        int v1_0 = b.get(0);
        int v1_1 = b.get(1);
        return !((v0_1 < v1_0) || (v0_0 > v1_1) || (v1_0 > v0_1) || (v1_1 < v0_0));
    }
}